﻿#pragma	once
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <stdexcept>  // 用于抛出异常   //standard exceptions（标准异常）库
using namespace std;

template<class K, size_t M>//M是B树阶，每个节点最大分支/孩子个数
struct BTreeNode
{
	// // 为了方便插入以后，检测到超出了，再分裂，？？？？所以多给一个空间？？；
	// 允许节点暂时"超载"，存储 M 个关键字（超过限制 1 个）
	// 当 _n(关键字个数) == M 时立即分裂：
	// 分裂成两个节点，各约有 M/2 个关键字
	// 将中间关键字提升到父节点
	// 这样保证分裂后，所有节点都满足 B 树的定义（最多 M-1 个关键字）
	//
	//还有个好处，
	//这样可以把分支/孩子个数num; ceil(M/2) <= num <= M
	//转换为 (M+1)/2 <= num <= M 方便计算
	//还有 M/2得到 keys的mid，都能保证分裂后 剩余的 满足ceil(M/2) <= num <= M


	//BTreeNode<K, M> 或 BTreeNode 都行
	BTreeNode* _parent = nullptr;
	K _keys[M] = { K() };//多开一个，方面延迟判断，代码好写点
	BTreeNode<K, M>* _subs[M + 1] = { nullptr };//孩子指针；叶子节点里也可以存孩子指针（最后一层孩子指针）
	int _size_cur_key = 0;//实际当前存储的key个数

	BTreeNode() = default; //强制生成默认无参构造函数

	BTreeNode(K key, BTreeNode<K, M>* ptr_child, BTreeNode<K, M>* parent)
	{
		//新节点 的第一个 key, ptr_child
		_keys[0] = key;
		_subs[0] = ptr_child;
		_size_cur_key = 1;
		_parent = parent;
	}

	// 析构函数 - 递归释放所有子节点
	~BTreeNode()
	{
		for (int i = 0; i <= _size_cur_key; ++i) {
			if (_subs[i]) {
				delete _subs[i];  // 递归删除子节点
				_subs[i] = nullptr;
			}
		}
	}

};



//我们下面写的这个BTree 每个非根节点，分支/孩子节点 使用率 是 约50%~100%；
//若要严格 >= 50%, 则 代码复杂会很多，得不偿失，没必要，---------------错，下面写的就是严格 >= 50%的
template<class K, size_t M>
class BTree
{
	using Node = BTreeNode<K, M>;
	using NodePtr = Node*;
public:
	// 构造函数
	BTree() : _root(nullptr) {}

	// 析构函数
	~BTree()
	{
		if (_root) {
			delete _root;  // 这会触发节点的递归删除
			_root = nullptr;
		}
	}


	//当前用的是顺序查找，用二分会更高效
	//找key, 同时带出 最终有效查找的节点 （可能找到，也可能没）
	pair<Node*, int> Find(const K& key)
	{
		if (_root == nullptr)
		{
			cerr << "Find error, _root == nullptr" << endl;
			exit(-1);
		}
		Node* parent = nullptr;
		Node* cur_node = _root;
		while (cur_node)
		{
			size_t i = 0;
			int sz = cur_node->_size_cur_key;
			for (; i < sz; i++)
			{
				if (key == cur_node->_keys[i])
				{
					return make_pair(cur_node, 1); //{cur_node, 1}
				}
				else if (key < cur_node->_keys[i]) // 去 cur_node->_keys[i]的左孩子中 找;  i是左孩子，i+1是右孩子
				{
					parent = cur_node;
					cur_node = cur_node->_subs[i];
					break;
				}
				//key > cur_node->_keys[i] 时，i++, 向后找
			}

			if (i == sz) //说明key 比当前节点的所有关键字都大
			{
				//去 最后一个关键字的右孩子中 找
				parent = cur_node;
				cur_node = cur_node->_subs[i];//i 最后一个节点右孩子，_subs的最后一个元素
			}
			else //key < cur_node->_keys[i] 
			{
				//去下一层找
			}
		}

		return make_pair(parent, -1);//没找到时，parent是最终有效查找的节点，也是B树叶子节点, 插入时，key就是插到这个节点
	}


	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			//Node* newNode = new Node;
			//newNode->_size_cur_key = 1;
			//newNode->_keys[0] = key;
			//newNode->_subs[0] = nullptr;
			//newNode->_parent = nullptr;

			//或

			Node* newNode = new Node(key, nullptr, nullptr);
			_root = newNode;
			return true;
		}

		//当BTree 不是空 时，Find找不找的到，返回的kv.first都一定不是空；若找到返回的是所在节点指针；若找不到，返回的是即将让key插入的叶子节点指针
		pair<Node*, int> kv = Find(key);
		if (kv.second >= 0)
		{
			// 改为抛出异常而不是仅打印错误信息
			throw std::invalid_argument("Key " + to_string(key) + " already exists in B - Tree");
			// 或者可以选择返回false
			//cerr << "已存在，无法再插入" << endl;
			//return false;
		}

		//kv.second < 0   未找到
		Node* insert_node = kv.first;//key插入的一定是个叶子节点
		// 循环每次往cur插入 new_key和right_child
		K new_key = key;
		NodePtr right_child = nullptr;//循环向上插入时，new_key有个右孩子
		Node* newRight = nullptr;//防止 进行第二次循环时，上次的newRight因一趟循环结束调析构销毁
		while (1)  //为了循环向上检查/插入
		{
			_InsertKey(insert_node, new_key, right_child);//先插入，延迟检查（有利于集中处理）//一定能插入成功；因为一开始多开了个空间

			// 检查节点关键字数量是否符合B树规则
			// 非根节点关键字数量应在 [ceil(M/2)-1, M-1] 范围内
			// 根节点关键字数量可以在 [1, M-1] 范围内
			if (insert_node->_size_cur_key < M)//M是最大分支数
			{
				// 节点未满，不需要分裂
				return true;
			}

			//分裂---先右 后上，因为上要连新的右孩子
			//右半边关键字给新产生的兄弟，新兄弟也要连到父节点合适的位置中，中间给父节点  //每个关键字对应的孩子指针也要带过来
			else //==
			{
				int mid = M / 2;// [mid+1, M)给新兄弟  M是总个数，不是下标

				//构建新兄弟， 
				int start = mid + 1;
				int nRight = M - start;//右兄弟key数 
				newRight = new Node;

				for (size_t i = 0; i < nRight; i++)
				{
					//Node*& 有的丑，重命名一下改成了NodePtr&
					int& key = insert_node->_keys[start + i];
					NodePtr& left_child = insert_node->_subs[start + i]; //必须用引用，否则后面修改的不是原数据，只是新局部变量
					newRight->_keys[i] = key;
					newRight->_subs[i] = left_child;//左孩子也连过来

					//被移动的孩子们 的parent 也要改
					if (left_child)//存在
					{
						left_child->_parent = newRight;
					}

					// 被拷走的节点处，重置为默认值，方便观察 剩下的有效节点，
					key = K();
					left_child = nullptr;
				}
				//nRight是newRight 最后一个孩子（右孩子）下标
				right_child = insert_node->_subs[start + nRight];//_subs[M]//下标M,即最后一个孩子（右孩子）
				newRight->_subs[nRight] = right_child;
				if (right_child)//存在
				{
					right_child->_parent = newRight;
				}
				right_child = nullptr; // 被拷走的节点处，重置为默认值，方便观察 剩下的有效节点，

				//更新节点的 _size_cur_key
				newRight->_size_cur_key = nRight;
				insert_node->_size_cur_key -= nRight;//后nRight个给了右兄弟

				/****************************************************************/
				K mid_key = insert_node->_keys[mid];
				insert_node->_keys[mid] = K();
				insert_node->_size_cur_key--;//中间一个给父

				//检查是否有 父节点，
				// 若没有(说明当前节点之前没有兄弟)，新建个节点做新根
				if (!insert_node->_parent)
				{
					//mid是下标
					//新建个节点做新根
					_root = new Node(mid_key, insert_node, nullptr);//key, subs, parent
					_root->_subs[1] = newRight;//右孩子(刚刚的新兄弟)

					insert_node->_parent = _root;
					newRight->_parent = _root; //新兄弟 也要连到父节点合适的位置上

					//不用再向上检查了（不用检查新节点/父节点key是否满了）; 
					break;
				}

				//有父节点，则将mid_key遍历插到合适的位置，
				else
				{
					//将mid_key遍历插到parent的合适位置 转换为 插入到新insert_node的合适位置

					new_key = mid_key;
					right_child = newRight;
					insert_node = insert_node->_parent;
				}
				int a = 0;
			}
			int b = 0;

		}

		return true;
	}

	void InOrder()
	{
		_InOrder(_root);//里面再套一个_InOrder，外面调InOrder时就不用传参了
	}

private:
	//纯粹的插入key
	void _InsertKey(Node* node, const K& key, Node* ptr_child)//ptr_child是key的右孩子
	{
		int i = node->_size_cur_key - 1;
		while (i >= 0 && key < node->_keys[i]) //不会有==，因为前面已经不允许重复了
		{
			//_keys[i] 和 它右孩子_subs[i+1] 都右移
			node->_keys[i + 1] = node->_keys[i];
			node->_subs[i + 2] = node->_subs[i + 1];
			i--;
		}
		//key 刚好 > node->_keys[i]  或 遍历了一遍都比key大，i现在== -1
		node->_keys[i + 1] = key;
		node->_subs[i + 1 + 1] = ptr_child;//向上更新过程中，key的右孩子(之前的新兄弟)，一定恰好在key的的右孩子处，不用和node的其它关键字/孩子 比较，画一下图就知道了

		if (ptr_child)//如果ptr_child指针不为空，就是有孩子
		{
			ptr_child->_parent = node;
		}

		node->_size_cur_key++;//实际关键字个数++
	}

	void _InOrder(NodePtr cur)
	{
		if (cur == nullptr)
		{
			return;
		}

		for (size_t i = 0; i < cur->_size_cur_key; i++)
		{
			_InOrder(cur->_subs[i]);//左
			cout << cur->_keys[i] << " ";
		}

		int right = cur->_size_cur_key;
		_InOrder(cur->_subs[right]);//cur最后的右孩子

	}

private:
	Node* _root = nullptr;

};

void TestBTree()
{
	//int a[] = { 53, 139, 75, 49, 145, 36, 101 };
	//BTree<int, 3> t;//路数/阶数
	//for (auto e : a)
	//{

	//	t.Insert(e);
	//	cout << "刚插入" << setw(4) <<  e << "后: ";
	//	t.InOrder();
	//	cout << endl;
	//}
	//cout << setw(14) << "总: ";//一个汉字占两个字宽
	//t.InOrder();


	try
	{
		int a[] = { 53, 139, 75, 49, 145, 36, 101 };
		BTree<int, 3> t;
		for (auto e : a)
		{
			t.Insert(e);// 可能抛出异常的操作
			cout << "刚插入" << setw(4) << e << "后: ";
			t.InOrder();
			cout << endl;
		}
		cout << setw(14) << "总: ";//一个汉字占两个字宽
		t.InOrder();

		//故意测试重复键
		t.Insert(53);  // 这会抛出异常
	}

	//当插入重复键53时，Insert()会抛出异常
	//程序流立即跳转到catch块
	//打印出类似"Error: Key already exists in B-Tree"的信息
	//防止程序因未处理异常而崩溃
	catch (const std::exception& e)// 捕获所有标准异常
	{
		cerr << "\nError: " << e.what() << endl;//e.what()：获取异常的描述信息
	}

	//try - catch 基本结构，一起用于捕获和处理可能发生的异常
	// try块​​：包含可能抛出异常的代码, 如果其中任何语句抛出异常，立即跳转到匹配的catch块
	//try {
	//	// 可能抛出异常的代码
	//}
	//catch (const 异常类型& e) {  //捕获这种异常类型这的所有异常
	//	// 异常处理代码   //e.what()：获取异常的描述信息
	//}
	//异常处理的好处​​：
	//	将错误处理与正常逻辑分离
	//	避免多层嵌套的错误检查
	//	提供统一的错误处理机制
}

int main()
{
	TestBTree();

	return 0;
}